package zhengqc.sort.merge_sort;

import zhengqc.sort.Sort;

import java.util.Arrays;

public class MergeSort<E extends Comparable<E>> extends Sort<E> {
    private E[] tempArray;
    public MergeSort() {
        this.sortName = "MergeSort";
        this.tempArray = null;
    }
    private void sort(E[] array, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;  // int mid = (left + right) >> 1;
        sort(array, left, mid);
        sort(array, mid+1, right);
        // 若每次归并的两个小数组都是有序的, 即 a[mid]<=a[mid+1] 时, 数组整体有序, 则不必进行 merge 操作
        if (array[mid].compareTo(array[mid+1]) > 0) {
            merge(array, left, mid, right);
        }
    }
    /* 合并两个有序的区间 array[left...mid] 和 array[mid+1...right] */
    private void merge(E[] array, int left, int mid, int right) {
        System.arraycopy(array, left, this.tempArray, left, right-left+1);
        int i = left, j = mid+1;
        // 每轮循环为 array[k] 赋值
        for (int k = left; k <= right; ++k) {
            if (i > mid) {
                array[k] = this.tempArray[j];  ++j;
            } else if (j > right) {
                array[k] = this.tempArray[i];  ++i;
            } else if (this.tempArray[i].compareTo(this.tempArray[j]) <= 0) {
                array[k] = this.tempArray[i];  ++i;
            } else {
                array[k] = this.tempArray[j];  ++j;
            }
        }
    }
    @Override
    public void sort(E[] array) {
        // 这里对归并排序过程中用到的临时数组预先分配空间
        this.tempArray = Arrays.copyOf(array, array.length);
        sort(array, 0, array.length-1);
        this.tempArray = null;
    }
}
